package _08_DFS_BFS;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _40_组合总和II {

    public static void main(String[] args) {

        int[] ins = new int[]{10, 1, 2, 7, 6, 1, 5};

        _40_组合总和II v = new _40_组合总和II();

        List<List<Integer>> lists = v.combinationSum2(ins, 8);

        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }

    private List<List<Integer>> results = new ArrayList<>();


    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 排序
        Arrays.sort(candidates);
        dfs(candidates, 0, target, new ArrayList<>());
        return results;
    }


    public void dfs(int[] candidates, int index, int target, List<Integer> list) {
        if (target == 0) {
            // 找到元素，添加集合中
            results.add(new ArrayList<>(list));
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            if (target < candidates[i]) break;
            // 去重操作 i > index, 如果是循环第二次挑选，如果重复continue
            if (i > index && candidates[i] == candidates[i - 1]) continue;
            list.add(candidates[i]);
            dfs(candidates, i + 1, target - candidates[i], list);
            // 回溯
            list.remove(list.size() - 1);
        }
    }


}
